// hard

// 给定一个链表数组，每个链表都已经按照升序排列
// 要求，将所有链表合并到一个升序链表中，返回合并后的链表

// 解题思路，将链表数组不断二分，转为规模二分之一的子问题，然后再进行归并排序
const {ListNode, LinkedList} = require('../../1. 链表基础/1. 建立线性链表')

function merge_sort(lists, left, right) {
    if (left === right) {
        return lists[left]
    }
    let mid = left + Math.floor((right - left) / 2)
    let node_left = merge_sort(lists, left, mid)
    let node_right = merge_sort(lists, mid + 1, right)
    return merge(node_left, node_right)
}

function merge(a, b) {
    let root = new ListNode(-1)
    let cur = root
    while (a && b) {
        if (a.val < b.val) {
            cur.next = a
            a = a.next
        } else {
            cur.next = b
            b = b.next 
        }
        cur = cur.next
    }
    if (a) {
        cur.next = a
    }
    if (b) {
        cur.next = b
    }
    return root.next
}

function mergeKLists(lists) {
    if (!lists || lists.length === 0) {
        return null
    }

    let size = lists.length
    return merge_sort(lists, 0, size - 1)
}

let lists = [new LinkedList([1,4,5]).head, new LinkedList([1,3,4]).head, new LinkedList([2, 6]).head]
let result = mergeKLists(lists)
// let result = mergeKLists([])
console.log(result)